package com.LC._33;

class Solution {
    //    public int search(int[] nums, int target) {
//    int left = 0;
//    int right = nums.length - 1;
//    while (left <= right) {
//        int mid = (left + right) / 2;
//        if(nums[mid] == target) {
//            return mid;
//        }
//
//        //与中间值比较时-> 用>||<
//        if(nums[mid] < target&&target<=nums[right]) {//右偏右
//            left = mid + 1;
//        }else if(nums[mid] > target&&target<=nums[right]){//右偏左
//            right = mid -1;
//        }else if(nums[mid] < target&&target>=nums[left]){//左偏右
//            left = mid +1;
//        }else if(nums[mid] > target&&target>=nums[left]){//左偏左
//            right = mid -1;
//        }
//    }
//    return  -1;
//    }
    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) return -1;
        int left = 0, right = len - 1;
        // 1. 首先明白，旋转数组后，从中间划分，一定有一边是有序的。
        // 2. 由于一定有一边是有序的，所以根据有序的两个边界值来判断目标值在有序一边还是无序一边
        // 3. 这题找目标值，遇到目标值即返回
        // 4. 注意：由于有序的一边的边界值可能等于目标值，所以判断目标值是否在有序的那边时应该加个等号(在二分查找某个具体值得时候如果把握不好边界值，可以再每次查找前判断下边界值，也就是while循环里面的两个if注释)
        while (left <= right) {
            // if(nums[left] == target) return left;
            // if(nums[right] == target) return right;

            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if(nums[left]<nums[mid]){//
                if(nums[left]<=target&&target<nums[mid]){
                    right = mid -1;
                }else{
                    left =mid +1;
                }
            }else{
                if(nums[right]>=target&&target>nums[mid]){//
                    left = mid +1;
                }else{
                    right=mid -1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{4, 5, 6, 7, 0, 1, 2};
        System.out.println(solution.search(nums, 0));
    }
}
